• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The subject of the invention is a countermeasure method for an electronic component implementing a public key cryptography algorithm on an elliptic curve E defined on a field K and comprising an iterative scalar multiplication operation making it possible to obtain a point [k ] P from a point P of the curve E and an integer k to remain secret, the power consumption of the electronic component depending on the value taken by at least one critical point used in said operation to iteratively determine the point [k] P. The method comprises: a step of providing (500) at least one power of a constant non-zero predefined K element and not more than one; a step of initializing (501) the coordinates of the at least one critical point to a predefined value; a step implementing the scalar multiplication operation (502), the coordinates associated with at least one critical point being modified at each iteration by multiplying at least one of the coordinates of this point by the at least one power of the element c obtained at the supply step (500).
    公开号:FR3017476A1
    申请号:FR1451096
    申请日:2014-02-12
    公开日:2015-08-14
    发明作者:Cedric Murdica；Sylvain Guilley
    申请人:Secure IC SAS；
    IPC主号:
    专利说明:

    [0001] The invention relates to a countermeasure method for an electronic component implementing a public-key cryptography algorithm on an elliptic curve, an electronic component and an electronic component. system implementing the method. It applies to the field of cryptography on elliptic curves. Elliptic curve cryptography makes it possible to generate signatures, to encrypt digital messages or to establish encryption keys. The activity of the electronic circuits is observable during their operation through physical quantities such as power consumption, calculation time or electromagnetic radiation. These physical quantities depend on both the computational architectures and the data manipulated inside the circuit. Information on the processed data is thus indirectly available outside the circuit by observing said quantities called hidden channels or auxiliary channels. The dissipation of these physical quantities may jeopardize the security of systems processing secret data protected in particular by cryptographic methods. Thus, if secret data is protected using a secret encryption key cryptography algorithm, the robustness of the protection lies in the ability to keep said key actually secret. The dissipation of the physical quantities may allow a third party to obtain said key by implementing appropriate attacks and, consequently, to access the secret data. An attack by observing physical quantities dissipated by said circuit is usually referred to as hidden channel attack. In the remainder of the description, a third party using observation attack methods to access data that is not intended for him is called an attacker, while the physical quantities dissipated are called leaks or hidden channels. Today, there are powerful observation attacks allowing access to data processed by protected circuits. These methods make it possible to bypass the security conferred at the mathematical level by cryptography. Cryptographic applications based on elliptic curves usually use Elliptic Curve Scalar Multiplication (ECSM) as the main operation. This operation determines a scalar [k] P = P + P + - .. + P from a point P and an integer k. The point P is usually a public datum, while the integer k is a secret. The ECSM elliptic curve scalar multiplication operation can be implemented using several methods belonging to the state of the art, among which the scalar multiplication technique with left-to-right window (see FIG. 1), the Montgomery scale (see Figure 2), and the so-called right-to-left sliding-window Scaling Multiplication technique in WNAF (see Figure 3). These methods usually operate bit by bit. Basic elliptic curve operations such as addition or doubling as well as points used (pre-calculated or dynamic) depend on the current bits. Some hidden channel attacks are very powerful because a single observation of ECSM multiplication is sufficient to determine all the bits of the scalar. There is one attack that can be used against elliptic curve cryptography methods which is to determine which values are manipulated during a specific operation by comparing sub-traces of current consumption. Such an attack is referred to as horizontal. One example is the Big Mac attack, but there are others, like the SVA (Same-Values Analysis) attack described in the article in the article by C. Murdica, S. Guilley, J.- L. Danger, P. Hoogvorst and D. Naccache entitled Sliding Windows Succumbs to Big MacAttack, Workshop on Constructive Side-Channel Analysis and Secure Design, 2012. Knowing what values are manipulated reveals information about the scalar. This attack is implemented by comparing the power consumption at different iterations of the ECSM. Since current consumption is correlated with manipulated values, the attack consists of detecting whether the same values are manipulated at different times of the ECSM scalar multiplication calculation.
    [0002] In the case of the Montgomery scale (see Figure 2), Q [0] is operand 1 on addition (operands 1 and 2 of an addition are not used in the same way). Q [0] will be the doubling input only if ki = 0. In the case of right-left sliding window scalar multiplication in wNAF (see Figure 3), it is a question of detecting whether the R point is used twice during the same iteration. The analysis of the result of the addition of an iteration and the entry of the addition of the following iterations can also reveal information. This type of attack is very powerful because the knowledge of the base point is not necessary and a single trace makes it possible to recover the entire scalar. Thus, the randomization countermeasures of the starting point or randomization of the scalar are ineffective. In addition, this type of attack can be adapted to other ECSM operations. This type of attack is called "Big-Mac" and is featured in the Walter CD article entitled Same 25 Values Power Analysis Using Special Points on Elliptic Curves, Workshop on Cryptographic Hardware and Embedded Systems, 2001. One of the goals of the The invention is to overcome shortcomings / drawbacks of the state of the art and / or to make improvements thereto.
    [0003] For this purpose, the subject of the invention is a countermeasure method for an electronic component implementing a public key cryptography algorithm on an elliptic curve E defined on a body III and comprising an iterative scalar multiplication operation making it possible to obtain a point [k] P from a point P of the curve E and an integer k to remain secret, the power consumption of the electronic component depending on the value taken by at least one critical point used in said operation for iteratively determining the point [k] P, the method comprising: a step of providing at least one power of a constant nonzero predefined constant element c of a different one; a step of initializing the coordinates of the at least one critical point to a predefined value; a step implementing the scalar multiplication operation, the coordinates associated with at least one critical point being modified at each iteration by multiplying at least one of the coordinates of this point by the at least one power of the element c obtained at l supply step (500). According to one embodiment, the element c is chosen less than or equal to half the cardinality of the basic group of the curve. According to one embodiment, the element c is chosen of order O strictly greater than three times the number of iterations of the scalar multiplication so as to prevent the element one from intervening during the successive multiplications of powers of c. . According to one embodiment, the multiplications by the following powers c, c 2, c 3, c 4 and c 6 are determined by the use of addition chains, c being chosen so as to minimize the length of said additive chains. According to one embodiment, the coordinates associated with at least one critical point are modified by projection equivalence.
    [0004] According to one embodiment, the coordinates associated with at least one critical point are modified by the implementation of an isomorphism cf) between the curve E and a second elliptic curve E '. According to one embodiment, the scalar multiplication operation is implemented by scalar multiplication with a window from left to right, the window being of size w. According to one embodiment, the scalar multiplication operation is implemented by a Montgomery scale. According to one embodiment, the scalar multiplication operation is implemented by scaling right-to-left sliding window scaling in wNAF. According to one embodiment, the scalar multiplication operation is implemented with the following steps: zero initialization of the coordinates of a point Q used as a working variable and corresponding to a partial scalar multiplication; - pre-calculation of 2w multiple R [j] of P with j = 1 ... 2w; doubling Q and adding R [v] to Q with sliding window 20, the countermeasure being implemented by modifying at each iteration i the coordinates (XR [v], YR [v], ZR [v]) of the point R [v] with v (ki, ..-, ki-w + 1) 2 using the following expression: (XR p1, YR ['], ZR ['] - (c2XR c3 YR ['], cZR According to one embodiment, the scalar multiplication operation is implemented with the following steps: zero initialization of the coordinates of a point Q used as a working variable and corresponding to a partial scalar multiplication; Pre-calculating 2w multiple R [j] of P with j = 1 ... 2w, doubling of Q and adding R [v] to Q with sliding window (603), the countermeasure being implemented by modifying the coordinates (XQ, YQ) and (XRup YR [i]) of points R [j] and Q at each iteration as follows: i (XQ, YQ) = (c24, c3YQ) ii for j ranging from 1 at 2w, (XR [i], YRU]) = (u2XRupu3YRui) The subject of the invention is also a electronic public key cryptographic system on an elliptic curve E defined on a body III, implementing a scalar multiplication operation to obtain a point 10 [k] P from a point P of the curve E and d an integer k to remain secret, the power consumption of said component depending on the value taken by at least one critical point used in said operation to iteratively determine the point [k] P, the circuit comprising at least one module adapted so to: providing a constant pre-defined element c of non-zero and different from one; initialize coordinates of the at least one critical point to a predefined value; implementing the scalar multiplication operation, the coordinates associated with at least one critical point being modified at each iteration by multiplying at least one of the coordinates of this point by a power of the element c. According to one embodiment, the electronic circuit comprises an internal memory in which element c is stored. According to one embodiment, calculation procedures corresponding to the addition strings required for updating the coordinates of the at least one critical point are pre-calculated and stored in the internal memory of the component. The invention also relates to a public key cryptography system 30 on an elliptic curve E defined on a body III comprising an electronic circuit as described above and a memory external to said circuit in which the element c is stored. According to one embodiment, calculation procedures corresponding to the addition strings required for updating the coordinates of the at least one critical point are pre-calculated and stored in the external memory. The invention also relates to a computer program comprising instructions for executing the method described above, when the program is executed by a data processing module. Other features and advantages of the invention will become apparent from the following description given by way of nonlimiting illustration, with reference to the appended drawings in which: FIG. 1 gives an example of implementation of FIG. scalar multiplication on ECSM elliptic curve using scalar multiplication technique with window; FIG. 2 gives an example of implementation of ECSM elliptic curve scalar multiplication using a Montgomery scale; FIG. 3 gives an example of implementation of scalar multiplication on elliptic curve ECSM using a sliding window from right to left in wNAF; Figure 4 gives an example of a trace generated by the scalar multiplication technique with a window of length two; Figure 5 is a diagram illustrating in a simplified manner the method according to the invention; FIG. 6 gives an example of implementation of a countermeasure method for an electronic component implementing a public key cryptography algorithm on an elliptic curve E with updating of the coordinates of the points by equivalence in projective properties; FIG. 7 gives an example of implementation of a countermeasure method for an electronic component implementing a public key cryptography algorithm on an elliptic curve E with updating of the coordinates of the points by isomorphism; FIG. 8 shows an electronic system that can implement the countermeasure method according to the invention.
    [0005] FIG. 1 gives an example of implementation of ECSM elliptic curve scalar multiplication using the window scalar multiplication technique. The data used in input 100 are: an integer k corresponding to the private key (herei, 1, ..., ko) 2 expressed in base two; a point P of the curve usually corresponding to a public datum; an integer w corresponding to the size of the window.
    [0006] It should be noted that w is chosen with win. If this is not the case, the scalar is padded with zeros to the left. In a first step 101, a point Q used as a working variable and corresponding to a partial scalar multiplication is initialized to zero.
    [0007] In a second step 102, 2W multiples R [j] of P are pre-calculated. A third step 103 is then applied so as to perform a sliding window doubling and adding treatment of length w usually designated by the expression "sliding window double-30 and-add".
    [0008] The value taken at the end of step 103 by the variable Q is then returned as a result and corresponds to the scalar [k] P. FIG. 2 gives an example of implementation of ECSM elliptic curve scalar multiplication using a Montgomery scale. The data used at input 200 are: an integer k corresponding to the private key (1c, _1, k0) 2 expressed in base two; a point P of the curve usually corresponding to a public datum. In a first step 201, two working variables Q [0] and Q [1] corresponding to two partial scalar multiplications are respectively initialized to zero and P. A second step 202 performs the calculation by scale and the value taken by the variable 15 Q [0] at the end of the step is then proposed 203 as a result and corresponds to the quantity [k] P. FIG. 3 gives an example of implementation of ECSM elliptic curve scalar multiplication using a left-right sliding window in wNAF. The NAF (Non-Adjacent Form) representation of size w of a positive integer k corresponds to the following expression: k = k i2i in which: each coefficient ki different from 0 is odd; -2w-1 <ki <2w-1; # 0; at most one of w consecutive coefficients is different from zero. This representation is useful in some cases of exponentiation because it is peculiar to contain few elements different from zero.
    [0009] The data used at the input 300 of this method are: the representation NAF of the size of the window k = (k1-1, ---, ko) w-NAF; a point P of the curve usually corresponding to a public data.
    [0010] A first step 301 initializes a variable m and a variable R serving as a power accumulation register of P. A second step 302 initializes m variables Q [] of partial scalar multiplication to zero. A step 303 updates the variables Q [] by additions and subtractions of powers of P. The function abs () is a function returning the absolute value of its input parameter. In this step, the doubling of the accumulation register R is performed at each iteration of the incrementing loop on the variable i. A step 304 implements a post-calculating phase that iteratively determines Q [1] by adding a partial multiplication j. Q [j]. The value taken at the end of step 303 by the variable Q [1] is then returned 304 as a result and corresponds to the point [k] P. Figure 4 gives an example of a trace generated by the scalar multiplication technique with a window of length two. For w = 2, R [1], R [2] and R [3] have the following values: R [1] = [(0 1 -)] 2P R [2] = [(1 0)] 213 R [3] = [(1 1 -)] 2P 3 0 1 74 76 11 In this simple example given by way of illustration, the scalar k is the following: k = (10 10 11 01 10) 2 5 [k] P will be calculated as follows: [k] P = 4 (4 (4 (4R [2] + R [2]) + R [3]) + R [1]) + R [2] The scalar k can be easily deduced if an attacker is able to determine which point among R [1], R [2] or R [3] is added to Q at each iteration. For this, the current consumption at the different iterations of the ECSM multiplication is estimated. The Big-Mac attack exploits the fact that power consumption is correlated with the values of the summed point. In the example of FIG. 4, if the electrical consumption records 401, 402 corresponding to two successive iterations of the step 103 are correlated, this means that: (kn_1, kn_2) = (kn-3, kn-4 ) If the power consumption readings 401, 402 are not correlated, 20 it means instead that: (kn-1, kn-2) # (kn-3, kn-4) The Big-Mac attack aims to to detect if the same values are manipulated at different times of the scalar multiplication calculation in order to go back to the secret k.
    [0011] To counteract this type of attack, the cryptographic method according to the invention comprises a countermeasure mechanism based on a modification of the coordinates of at least one critical point after its use during scalar multiplication on an elliptic curve. For this, properties of elliptic curves are exploited. In this description, a point is critical when the observation of the variations in the electrical consumption of the electronic component resulting from the use of this point during the implementation of the scalar multiplication may reveal all or part of the scalar k.
    [0012] Figure 5 is a diagram illustrating in a simplified manner the method according to the invention. The invention relates to a countermeasure method in an electronic circuit implementing a public key cryptography algorithm on an elliptic curve. To do this, he applies a scalar multiplication operation on the elliptic curve E so as to obtain a point [k] P from a point P of E and an integer k while applying a countermeasure mechanism. This operation is based on the use of at least one critical point.
    [0013] The method according to the invention comprises a step 500 of providing at least one power of a predefined constant non-zero element c. This element c belongs to the body III and is different from one. By way of example, this step may make it possible to obtain the element c itself (which is in fact equivalent to the power of one of this element, ie c ^ 1). In an alternative embodiment, this step may make it possible to obtain a set of powers of c composed for example of cAl, c ^ 2 and c ^ 3. Thus, several powers of c can be stored in a cryptography circuit implementing the invention, which has the decisive advantage of making it difficult for a third party to detect the value of c used.
    [0014] In one embodiment, the element c is chosen of order O strictly greater than three times the number of iterations of the scalar multiplication so as to prevent the element one from intervening during the successive multiplications of powers of c. . As a reminder, the order of an element e of III is the smallest non-zero integer δ such that es = 1. One skilled in the art will understand without effort that other data may also be acquired during this step, among which the coordinates of the point P, the scalar k or the width w of the working window, if any.
    [0015] A step 501 of the method then initializes the critical point or points used for the implementation of the scalar multiplication. For this, and depending on the technique used for the implementation of the scalar multiplication, the coordinates of the critical point or points can be initialized to zero, with the coordinates of the point P or other suitable values.
    [0016] A step 502 implements the scalar multiplication operation on the elliptical curve E iteratively as well as the countermeasure associated with it. The countermeasure consists of modifying the coordinates of at least one critical point at each iteration. The coordinates are modified by multiplying at least one of them by a power of the element c acquired in step 500. The value of said element is for example stored in the electronic circuit or in an accessible memory of said circuit. Element c is predefined in the sense that it is chosen and stored before application of the method. The technique used for the implementation of the scalar multiplication can be chosen from the following algorithms: scalar multiplication with a left-to-right window, Montgomery scale, scalar multiplication with sliding window from right to left in wNAF. The method according to the invention comprises two preferred embodiments.
    [0017] A first preferred embodiment relies on updating the representative of at least one critical point so as to maintain an equivalence in projective property of the point before and after updating its coordinates.
    [0018] A second preferred embodiment is based on the isomorphism update of the representatives of the points used, that is to say their coordinates. Element c is predefined in the sense that it is chosen and stored before application of the method. For example, an electronic circuit implementing the method according to the invention will be assigned a value of c chosen at the time of its production and this value will be stored in the circuit. The designer of such a circuit can however assign different values of c for the different circuits that it produces. Advantageously, the assignment of a plurality of values c makes it possible to adjust the compromise between security and complexity of implementation. It should be noted that c must be different from one for the coordinates to be effectively modified. The updating of the coordinates of the critical point (s) can be done at different times: - at the beginning of iteration; - at the end of iteration; after an elliptic curve operation such as doubling or adding; - or within an elliptical curve operation.
    [0019] Because the update of the representative (s) of the critical points is made after each use of said point allows to protect the circuit against horizontal attacks. The effectiveness of the ECSM multiplication including this countermeasure mechanism depends in particular on the moment chosen to update the coordinates or the points. This moment can be chosen to avoid compromising security. As an example, if the atomicity countermeasure as presented in the article by Chevallier-Mames, B., Ciet, M., and Joye, M. titled Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity, IEEE Transactions on Computers, pages 760-768, 2004, is applied with right-to-left sliding window scalar multiplication in wNAF, the update can be advantageously applied after each atomic block. It should be noted that a method of randomizing coordinates of the starting point by coordinate equivalence is described in European Patent Publication EP1166494 B1. Randomization is usually a technique for introducing a random element into a data processing method. In this publication, an element of the body is drawn randomly, which makes it possible to randomize the starting point at the beginning of ECSM scalar multiplication. Another randomization method is disclosed in European Patent Publication EP1381936 B1 and is based in particular on a random draw of the initial curve by isomorphism. In this case, an element of the body is drawn randomly so as to randomize the curve and the points at the beginning of the ECSM scalar multiplication. Both of these methods can counteract DPA (Differential Power Analysis) and CPA (Chosen-Plaintext Attack) attacks. However, the Big-Mac attack and other so-called horizontal attacks can be considered even if these methods are implemented. As a reminder, an attack is called horizontal when it is performed on a single trace of a signal representative of the power consumption of the cryptographic circuit. An attack is said to be vertical when it is performed on a plurality of signal traces representative of the electrical consumption of the cryptographic circuit. In the context of the invention, the coordinates of at least one critical point are modified at each iteration of the scalar multiplication, which makes most horizontal attacks inoperative.
    [0020] Unlike these techniques, the method according to the invention uses a predefined constant for the updating of the coordinates, which brings several decisive advantages. Thus, the method according to the invention advantageously allows an implementation of reduced complexity compared to the state of the prior art cited above. Indeed, the generation of random numbers as such is complex. This usually requires the use of a TRNG generator (True Random Number Generator) or PRNG (PseudoRandom Number Generator) external to the electronic circuit implementing the elliptic curve cryptography method. In addition, these generators are vulnerable to generator blocking attacks as described in the article by T. Markettos and SW Moore entitled The Frequency Injection Attack on Ring-Oscillator-Based True Random Number Generators, CHES 2009, pages 317- 331. Another advantage is that the manner in which the multiplication of the coordinates of the critical point (s) by the constant predefined element (c) can be optimized can be optimized by using, for example, addition strings, which is not possible in the case a random draw. In addition, when the element used for the modification of coordinates 20 is drawn randomly, it can potentially be large. By way of illustration, there is a one in two chance that its most significant bit is equal to one. This will then have the effect of imposing a long and costly multiplication in terms of computing resources. FIG. 6 gives an example of implementation of a countermeasure method for an electronic component implementing a public key cryptography algorithm on an elliptic curve E with updating of the coordinates of the points by equivalence in projective properties.
    [0021] The points on elliptic curves are usually represented in Jacobian coordinates and called in this description projective coordinates. For a point P, the following notations are used: P = (X, Y, Z) In this embodiment, the equivalence in projective properties for an elliptic curve is used. The equivalence in projective properties means that if III is the basic body, the projective coordinate representation (X, Y, Z) of a point P is equivalent to the representations defined by (c2X, c317, cZ) with c E III * (III * being equal to the set III to which is removed the value zero). In other words, the same point P can be represented using several sets of coordinates, a set of coordinates that can also be called a point representative. Equivalence to projective properties means that any operation performed in the IK body with a first representative gives the same result as if it had been applied with a second equivalent representative in projective properties. In this embodiment of the invention, a predefined element c of the body III is used to update the representative of at least one point used for the implementation of the ECSM multiplication. This update is performed by modifying the set of coordinates associated with this point so as to respect the equivalence in projective properties. In one embodiment, c is small relative to the cardinality of the base group on which the curve is constructed. More precisely, the number of coding bits c is chosen to be less than or equal to half the cardinality of the basic group of the curve. For example, if the elements of the group are coded on 256 bits, the cardinality is 2256 and c can be chosen between 2 to 2128. This makes it possible to avoid the use of too important values and thus to reduce the complexity calculation provided by the change of coordinates. The value of c may advantageously be chosen equal to three. FIGS. 6 and 7 are diagrams giving two examples of implementation of the invention with an ECSM calculation by scalar multiplication with a window from left to right. The person skilled in the art can effortlessly envisage the implementation of the invention for other ECSM calculations, such as, for example, the Montgomery scale or the right-to-left sliding-window scalar multiplication technique in wNAF.
    [0022] The example of FIG. 6 is based on a ECSM calculation by scalar multiplication with a window. Thus, as already explained with the aid of FIG. 1, the method comprises in this embodiment input data 600 and implements steps 601 and 602 respectively corresponding to the input data 100 and in steps 101 and 102. A third step 603 is then applied to effect a wipe-window doubling and adding process of length w in the same manner as for step 103 but in addition to an update to the end of each iteration of the representative (XR [v], YR [v], ZR [v]) of the point R [v] having been used in this iteration respecting the equivalence in projective properties. It should be noted that an iteration corresponds to the processing carried out in a processing window. This update is performed as follows: (XR [v], YR [v], ZR [v]) <- (C2 XR [v], C3 YR [v], CZR [v]) The value taken at the end of step 603 by the variable Q [1] is then supplied 604 as a result and corresponds to the point [k] l 3.
    [0023] FIG. 7 gives an example of implementation of a countermeasure method for an electronic component implementing a public key cryptography algorithm on an elliptic curve E with updating of the coordinates of the points by isomorphism.
    [0024] An elliptic curve is defined by its reduced Weierstrass equation E given by the following expression: E: y2 = x3 + ax + b Let a second elliptic curve be defined by its reduced Weierstrass equation E 'given by the following expression: E ': y2 = x3 + a'x + b' It is shown that E is isomorphic to E 'if there exists c E III such that: a' = ac4 b '= bc6 In this case, the isomorphism cf ) between E and E 'is defined by the following expression: (p ((x, y, z)) = (c.2x, c3y, z) As for the previous embodiment based equivalence coordinate modification in projective properties, an element c belonging to the body III is previously chosen and stored in the electronic circuit implementing the method.
    [0025] After the use of the representative of a critical point (X, Y, Z) for an operation necessary for the implementation of the ECSM, cf) is applied and all the points representatives are updated. The parameters a, b are also updated if they are used for elliptic curve operations such as doubling or adding points. The example of FIG. 7 is based on a ECSM computation by scalar multiplication with window. Thus, as already explained with the aid of FIG. 1, the method comprises in this embodiment input data 700 and implements the steps 701 and 702 respectively corresponding to the input data 100 and at steps 101 and 102. A third step 703 is then applied to perform a sliding window add and drop processing of length w in the same manner as for step 103 but with a further update at the end of each iteration of the representative of the critical point Q using the following expression: (XQ YQ) (C.
    [0026] 2 C 3 YQ) In addition, the set of 2W representatives of the critical points R [j] are updated using the following expression: (XR [i], YR [j] (C 2 XR [j] Lastly, the parameters are updated after they have been used using the following expressions: a <- c4a b <- c6b A reverse isomorphism is applied 704 so as to retranscribe the coordinates of the The value taken at the end of step 704 by the variable Q is then provided 705 as a result and corresponds to the scalar [k] P. For each of the two alternatives described for changing the the coordinates of at least one critical point by the calculation of c2X, c3Y, cZ or c2X, c3Y can be performed using chains addition to optimize the calculation of multiplications in the body In both cases, the choice of a fart The value of c is particularly appropriate. In addition, it is preferable to choose an element such that the c, c2, c3, c4, c6 or c2, c3, c4, c6 multiplications can be performed by very short additive chains. More precisely, c is chosen less than or equal to half the cardinality of the basic group of the curve. In this way, the updating of the coordinates requires only a few additions in the body, which is much less expensive than to implement multiplications. For example, by choosing c = 3, a multiplication by c can be done in two additions in the basic body, a multiplication by c2 = 9 can be done in four additions, and a multiplication by c3 = 27 can be done to make six additions. The size of the additions chain for small numbers can be found at: http://oeis.org/A003313. The choice of c allows a large number of possible optimizations, including the chains of additions. Since the value of c is predefined and fixed, it is for example possible to determine in advance the calculation procedures corresponding to the addition strings required for the update of the coordinates of the critical points can be prepared to the advanced. Thus, these computation chains can advantageously be integrated in the electronic component implementing the cryptography operations based on elliptic curves. According to one aspect of the invention, the multiplications by the following powers c, c 2, and c 3 are determined by the use of additive chains, c being chosen in this case to minimize the length said chains. c ^ 2 and c ^ 3 respectively represent the powers of two and three of c. FIG. 8 shows an electronic system that can implement the countermeasure method according to the invention. This system includes a central processing unit (CPU) 801 connected to an internal communication bus 800. Random access memory (RAM) 807 is also connected to the BUS. The system further includes a mass storage device controller 802 whose function is to manage accesses to a mass memory, such as a hard disk 803. The mass memory stores computer program instructions and data. enabling the implementation of the process for assigning temporary authentication data. The mass memory can be composed of all forms of non-volatile memory, such as for example EPROMs, EEPROMs, flash memories, magnetic disks such as internal hard disks and removable disks, magneto-optical disks, and CD-ROM discs 804. The system also includes a network adapter 805 for managing access to a telecommunication network 806. Optionally, the device may also include haptic equipment 809 such as a control device. slider, keyboard or other similar equipment. Slider control equipment can thus be used in the device to allow the user to position a cursor at a given location on a screen 808. In addition, the cursor control device allows the user to select various commands and generate control signals. The cursor control device may be a mouse, one of the buttons of said mouse being used to trigger the generation of the input signals.
    权利要求:
    Claims (17)
    [0001]
    CLAIMS1- Countermeasure method for an electronic component implementing a public key cryptography algorithm on an elliptic curve E defined on a 1K body and comprising an iterative scalar multiplication operation for obtaining a point [k] P from a point P of the curve E and an integer k to remain secret, the power consumption of the electronic component depending on the value taken by at least one critical point used in said operation to iteratively determine the point [k] P , the method comprising: - a step of supplying (500) at least one power of a predetermined non-zero constant element 1K and different from one; a step of initializing (501) the coordinates of the at least one critical point to a predefined value; a step implementing the scalar multiplication operation (502), the coordinates associated with at least one critical point being modified at each iteration by multiplying at least one of the coordinates of this point by the at least one power of the element c obtained at the supply step (500).
    [0002]
    2. The method of claim 1 wherein the element c is chosen less than or equal to half the cardinality of the basic group of the curve.
    [0003]
    3. Method according to one of the preceding claim wherein the element c is chosen of order S strictly greater than three times the number of iterations scalar multiplication so as to prevent the element one does not intervene during the successive multiplications of powers of c.
    [0004]
    4. Method according to one of the preceding claims wherein the multiplications by the powers of c following c, c ^ 2, c ^ 3, c ^ 4 and c ^ 6 are determined by the use of chains of additions, c being chosen so as to minimize the length of said additive chains.
    [0005]
    5. Method according to one of the preceding claims wherein the coordinates associated with at least one critical point are modified by projection equivalence.
    [0006]
    6. Method according to one of the preceding claims wherein the coordinates associated with at least one critical point are modified by the implementation of an isomorphism cp between the curve E a second elliptic curve E '.
    [0007]
    7- Method according to one of claims 1 or 2 wherein the scalar multiplication operation is implemented by a scalar multiplication window from left to right, the window being of size w.
    [0008]
    8- Method according to one of claims 1 or 2 wherein the scalar multiplication operation is implemented by a Montgomery scale.
    [0009]
    9- Method according to claim 1 or 2 wherein the scalar multiplication operation is implemented by a right-to-left sliding-window scalar multiplication in wNAF.
    [0010]
    10- Method according to claims 3 and 5 wherein the scalar multiplication operation is implemented with the following steps: - initialization to zero (601) coordinates of a point Q used as a working variable and corresponding to a multiplication partial scalar; - pre-calculation (602) of 2W multiples R [j] of P with j = 1 ... 2w; - doubling Q and adding R [v] to Q with a sliding window (603), the countermeasure being implemented by modifying at each iteration i the coordinates VR [v], YR [4, ZR [v]) of the point R [v] with y = (ki,, k i_w + 1) 2 using the following expression: (XR [v], YR [v], ZR [v]) = (C2 XR [v], C3 YR [v], CZ R [v]).
    [0011]
    11- Method according to claims 4 and 5 wherein the scalar multiplication operation is implemented with the following steps: - initialization to zero (601) coordinates of a point Q used as a working variable and corresponding to a multiplication partial scalar; - pre-calculation (602) of 2W multiples R [j] of P with j = 1 ... 2w; doubling Q and adding R [v] to Q with a sliding window (603), the countermeasure being implemented by modifying the coordinates (XQ, YQ) and (XR [i], YR [i]) of the points R [j] and Q at each iteration as follows: i. (X-Q, YQ) = (C24, C3YQ) ii. for j ranging from 1 to 2W, VR [i], YR [i]) = (u2XR [i], u3YR [i])
    [0012]
    12-electronic public key cryptography circuit on an elliptical curve E defined on a body III, implementing a scalar multiplication operation to obtain a point [1c] 13 from a point P of the curve E and an integer k to remain secret, the power consumption of said component depending on the value taken by at least one critical point used during said operation to iteratively determine the point [k] P, the circuit comprising at least one module adapted so to: providing a non-zero constant pre-defined element c which is different from initializing coordinates of the at least one critical point to a predefined value; implementing the scalar multiplication operation, the coordinates associated with at least one critical point being modified at each iteration by multiplying at least one of the coordinates of this point by a power of the element c.
    [0013]
    13. An electronic circuit according to claim 12 comprising an internal memory in which the element c is stored.
    [0014]
    14. The electronic circuit according to claim 13, wherein calculation procedures corresponding to the addition strings required for updating the coordinates of the at least one critical point are pre-calculated and stored in the internal memory of the component.
    [0015]
    15- public key cryptography system on an elliptical curve E defined on an IK body comprising an electronic circuit according to one of claims 12 to 14 and a memory external to said circuit in which is stored the element c.
    [0016]
    An electronic system according to claim 15 wherein calculation procedures corresponding to the addition strings required for setting the coordinates of the at least one critical point are pre-calculated and stored in the external memory.
    [0017]
    17- computer program comprising instructions for the execution of the method according to one of claims 1 to 11, when the program is executed by a data processing module.
    类似技术:
    公开号 | 公开日 | 专利标题
    EP3117555B1|2020-01-22|Countermeasure method for an electronic component implementing an elliptic curve cryptography algorithm
    EP2215768B1|2019-08-21|Method and devices for protecting a microcircuit from attacks for obtaining secret data
    WO2014111647A1|2014-07-24|Cryptography method comprising an operation of multiplication by a scalar or an exponentiation
    EP1493078B1|2009-03-18|Cryptographic method protected against side channel attacks
    EP1166494A1|2002-01-02|Countermeasure procedures in an electronic component implementing an elliptical curve type public key encryption algorithm
    CN103221917A|2013-07-24|Protecting modular exponentiation in cryptographic operations
    FR3010210A1|2015-03-06|PROTECTION OF CALCULATION AGAINST HIDDEN CHANNEL ATTACKS
    EP2546737A1|2013-01-16|Protection of a modular exponentiation calculation by adding a random amount
    FR2977952A1|2013-01-18|PROTECTION OF A MODULAR EXPONENTIATION CALCULATION BY MULTIPLICATION BY A RANDOM QUANTITY
    FR2941798A1|2010-08-06|APPARATUS FOR CALCULATING A RESULT OF SCALAR MULTIPLICATION
    WO2001093014A1|2001-12-06|Countermeasure method in an electronic component using a public key encryption algorithm on elliptic curve
    EP1166495A1|2002-01-02|Countermeasure method in an electric component implementing an elliptical curve type public key cryptography algorithm
    CA2712178A1|2009-09-17|Countermeasure method and devices for asymmetric cryptography
    FR2997780A1|2014-05-09|CRYPTOGRAPHY METHOD COMPRISING A MODULAR EXPONENTIATION OPERATION
    EP2983083B1|2017-04-12|Elliptic curve encryption method comprising an error detection
    CA2712180A1|2009-09-11|Countermeasure method and devices for asymmetrical cryptography with signature diagram
    FR2888690A1|2007-01-19|CRYPTOGRAPHIC PROCESS FOR THE SECURE IMPLEMENTATION OF AN EXPONENTIATION AND ASSOCIATED COMPONENT
    WO2001028153A1|2001-04-19|Countermeasure method in an electronic component which uses an rsa-type public key cryptographic algorithm
    EP3435585A1|2019-01-30|Protection of an iterative calculation against horizontal attacks
    WO2014096363A1|2014-06-26|Chaotic sequence generator
    FR2977954A1|2013-01-18|PROTECTION OF CALCULATION ON ELLIPTICAL CURVE
    EP2599256B1|2014-03-19|Method and device for randomizing a secret key for protecting against attacks by auxiliary channels
    FR3010562A1|2015-03-13|DATA PROCESSING METHOD AND ASSOCIATED DEVICE
    FR3038473A1|2017-01-06|METHOD FOR CRYPTOGRAPHIC DATA PROCESSING AND ASSOCIATED COMPUTER PROGRAM
    FR3013476A1|2015-05-22|SECURING METHOD OF CRYPTOGRAPHY ON ELLIPTICAL CURVES
    同族专利:
    公开号 | 公开日
    CN106464483A|2017-02-22|
    WO2015121324A1|2015-08-20|
    US10374790B2|2019-08-06|
    EP3117555A1|2017-01-18|
    CN106464483B|2019-12-03|
    US20170180114A1|2017-06-22|
    FR3017476B1|2017-06-09|
    EP3117555B1|2020-01-22|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US20070177721A1|2003-07-22|2007-08-02|Fujitsu Limited|Tamper-proof elliptic encryption with private key|
    US20120008780A1|2008-02-26|2012-01-12|King Fahd University Of Petroleum And Minerals|Method for elliptic curve scalar multiplication|
    US6748410B1|1997-05-04|2004-06-08|M-Systems Flash Disk Pioneers, Ltd.|Apparatus and method for modular multiplication and exponentiation based on montgomery multiplication|
    US7069287B2|2000-09-19|2006-06-27|Worcester Polytechnic Institute|Method for efficient computation of odd characteristic extension fields|
    DE102006014353B4|2006-03-28|2007-11-22|Siemens Ag|Method for the reliable determination of data|
    KR100867989B1|2006-12-06|2008-11-10|한국전자통신연구원|SPA-resistant Left-to-Right Recoding and Unified Scalar Multiplication Methods|
    US8559625B2|2007-08-07|2013-10-15|Inside Secure|Elliptic curve point transformations|
    CN103441846B|2013-08-12|2016-08-10|国家密码管理局商用密码检测中心|A kind of ECC algorithm to P territory selects side channel energy in plain text to analyze method|FR3057369B1|2016-10-07|2018-10-19|Idemia Identity And Security|CRYPTOGRAPHIC PROCESSING METHOD COMPRISING A MULTIPLICATION OF A POINT OF AN ELLIPTICAL CURVE BY A SCALAR|
    WO2018145189A1|2017-02-13|2018-08-16|Infosec Global Inc.|Countermeasures and optimizations in elliptic curve cryptographic schemes|
    JP2018146766A|2017-03-06|2018-09-20|キヤノン株式会社|Scalar multiple arithmetic device, scalar multiple arithmetic method and program|
    CN107204856B|2017-08-01|2019-10-22|北京智慧云测科技有限公司|A kind of method and device detecting elliptic curve loophole|
    US10805081B1|2020-04-30|2020-10-13|ISARA Corporation|Processing batches of point evaluations in a supersingular isogeny-based cryptosystem|
    法律状态:
    2016-01-25| PLFP| Fee payment|Year of fee payment: 3 |
    2017-01-26| PLFP| Fee payment|Year of fee payment: 4 |
    2018-01-26| PLFP| Fee payment|Year of fee payment: 5 |
    2020-01-27| PLFP| Fee payment|Year of fee payment: 7 |
    2021-01-26| PLFP| Fee payment|Year of fee payment: 8 |
    优先权:
    申请号 | 申请日 | 专利标题
    FR1451096A|FR3017476B1|2014-02-12|2014-02-12|COUNTER-MEASUREMENT METHOD FOR AN ELECTRONIC COMPONENT IMPLEMENTING A CRYPTOGRAPHY ALGORITHM ON AN ELLIPTICAL CURVE|FR1451096A| FR3017476B1|2014-02-12|2014-02-12|COUNTER-MEASUREMENT METHOD FOR AN ELECTRONIC COMPONENT IMPLEMENTING A CRYPTOGRAPHY ALGORITHM ON AN ELLIPTICAL CURVE|
    PCT/EP2015/052908| WO2015121324A1|2014-02-12|2015-02-12|Countermeasure method for an electronic component implementing an elliptic curve cryptography algorithm|
    EP15703784.7A| EP3117555B1|2014-02-12|2015-02-12|Countermeasure method for an electronic component implementing an elliptic curve cryptography algorithm|
    CN201580008628.9A| CN106464483B|2014-02-12|2015-02-12|Countermeasure, electronic circuit and the electronic system of elliptic curve cryptography are realized for electronic component|
    US15/118,500| US10374790B2|2014-02-12|2015-02-12|Countermeasure method for an electronic component implementing an elliptic curve cryptography algorithm|
    [返回顶部]